import java.util.List;
//test
public class MaxSum {
//	public int getMaxSum2(List<Integer> list) {
//		int len = list.size();
//		int[][] maxSum = new int[len][len];
//		for (int i = 0; i < len; i++) {
//			maxSum[i][i] = list.get(i);
//		}
//		for (int i = 1; i <= len - 1; i++) {
//			for (int j = 0; j <= len - i - 1; j++) {
//				maxSum[j][j + i] = Integer.MIN_VALUE;
//				for (int k = j; k <= j + i - 1; k++) {
//					int temp = maxSum[j][k] + maxSum[k + 1][j + i];
//					maxSum[j][j + i] = maxSum[j][j + i] > temp ? maxSum[j][j
//							+ i] : temp;
//				}
//				System.out.println("maxSum[" + j + "][" + (j + i) + "] = "
//						+ maxSum[j][j + i]);
//			}
//		}
//		return maxSum[0][len - 1] > 0 ? maxSum[0][len - 1] : 0;
//	}

	public int getMaxSum(List<Integer> list) {
		int len = list.size();
		int maxSum = Integer.MIN_VALUE;
		for (int i = 0; i < len; i++)
			for (int j = i; j < len; j++) {
				int temp = 0;
				for (int k = i; k <= j; k++) {
					temp += list.get(k);
				}
				maxSum = maxSum > temp ? maxSum : temp;
			}
		return maxSum;

	}

	public int getMaxSum1(List<Integer> list) {
		int len = list.size();
		int maxSum = Integer.MIN_VALUE;
		for (int i = 0; i < len; i++) {
			int temp = 0;
			for (int j = i; j < len; j++) {
				temp += list.get(j);
				maxSum = maxSum > temp ? maxSum : temp;
			}
		}
		return maxSum;

	}
	public int getMaxSum2(List<Integer> list) {
		int len = list.size();
		if(len == 1) 
			return list.get(0);
		else {
			int center = (len - 1) / 2;
			int leftMax = getMaxSum2(list.subList(0, center + 1));
			int rightMax = getMaxSum2(list.subList(center + 1, len));
			int s1 = Integer.MIN_VALUE;
			int temp = 0;
			for(int i = center ; i >=0 ; i --) {
				temp += list.get(i);
				s1 = temp > s1 ? temp : s1;
			}
			int s2 = Integer.MIN_VALUE;
			temp = 0;
			for(int i = center + 1 ; i < len ; i++) {
				temp += list.get(i);
				s2 = temp > s2 ? temp : s2;
			}
			int midMax = s1 + s2;
			int result = leftMax > midMax ? leftMax : midMax;
			result = result > rightMax ? result : rightMax;
			System.out.println(result);
			return result;
		}
	}
}
